package com.julius.design.suanfa.dynamic;

/**
 * @author julius
 * @date 2021-10-29 上午 10:32
 * <p>
 *      股票最大利润
 *      假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 *      卖出价格必须大于买入价格
 *      https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
 * </p>
 */
public class MaxProfit {


    /**
     * 股票的最大利润  ,暴力解法
     * [7,1,4,5,2,6]  ---> 最大利润为 6-1 = 5
     * @param prices 价格列表
     * @return 返回最大利润
     */
    public static int maxProfit(int[] prices){

        //穷举所有利润，找出最大的，前面一天作为买入，在其后面选出一天作为卖出，然后计算利润，双指针（A --> 买入，B --> 卖出）
        int max = 0;
        for (int i = 0;i< prices.length-1;i++){
            //买入价格
            int inPrice = prices[i];
            for (int j = i+1;j < prices.length;j++){
                int outPrice = prices[j];
                if(outPrice >= inPrice){
                    int profit = outPrice - inPrice;
                    if(profit >= max){
                        max = profit;
                    }
                }
            }
        }
        return max;
    }

    /**
     * 动态规划解法 ，股票最大利润
     * [7,1,4,5,2,6]  ---> 最大利润为 6-1 = 5
     *
     *
     * 最优子结构    重叠子问题     状态转移方程
     * dp[i] 代表第i天卖出时的最大利润
     *
     * dp[i-1] 代表第i-1天卖出的最大利润
     *
     * 第i天卖出的最大利润 = 第i天的价格 - 前i-1填的最小价格
     *
     * 所以状态转移方程为：
     *
     * maxProfit = max(dp[i-1],price[i] - min(prices(0,i-1)))
     *
     * 第一天利润为 0   最低买入价格为  7
     * 第二天利润为 -6  最低买入价格为  7
     * 第三天利润为 3   最低买入价格    1
     *
     *
     * @param prices
     * @return
     */
    public static int dynamicMax(int[] prices){
        //临界条件判断
        if(prices == null || prices.length < 1){
            return 0;
        }

        //前i-1的最大利润
        int maxProfit = 0
                //前i-1天的最小买入价格
                ,minInPrice = prices[0];

        //遍历一次
        for (int i = 0,j = i+1; i < prices.length-1; i++,j++) {
            if(prices[i] <= minInPrice){
                minInPrice = prices[i];
            }
            //第i天卖出时的最大利润
            int profit = prices[j] - minInPrice;
            if(profit >= maxProfit){
                maxProfit = profit;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = new int[]{7,1,4,5,2,6};
        System.out.println(maxProfit(prices));
        System.out.println(dynamicMax(prices));
    }
}
